iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 19
1
Software Development

LeetCode30系列 第 19

[LeetCode30] Day19 - 6. ZigZag Conversion

  • 分享至 

  • xImage
  •  

題目

  • The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
P   A   H   N
A P L S I I G
Y   I   R
  • And then read line by line: "PAHNAPLSIIGYIR"

  • Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

解法

首先觀察一下:

numRows = 3:
P   A   H   N
A P L S I I G
Y   I   R
  • 可以看到逐列讀取:
    • P->A->H->N的index為 0->4->8->12,一次跳4。
    • A->P->L->S->I->I->G的index為1->3->5->7->9->11->13,一次跳2。
    • Y->I->R的index為 2->6->10,一次跳4。
numRows = 4:
P     I    N
A   L S  I G
Y A   H R
P     I
  • 可以看到逐列讀取:

    • P->I->N的index為 0->6->12,一次跳6。
    • A->L->S->I->G的index為1->5->7->11->13,可以看到2個跳值,4與2輪流。
    • Y->A->H->R的index為 2->4->8->10,可以看到2個跳值,2與4輪流。
    • P->I的index為3->9,一次跳6。
  • 我們能得到幾件事情:

    • 第一列與最後一列,只有一個跳值。
    • 中間列會有2個跳值 (numRows=3時沒有,但我們能把它想像成有2個,沒差)。
    • 最大跳值會是 numRows x 2 - 2 (numRows=3,最大跳4, numRows=4,最大跳6)

所以我們能用一個for loop,i為每列第一個index(依上面例子,開頭順序0,1,2,3),並找出跳的規律,就解決問題了!。
至於2個跳值應該多少,大家就自己觀察一下啦!

Code

class Solution {
public:
    string convert(string s, int numRows) {
        
        int max_increase; //最大跳值
        int inc0, inc1; //2個跳值
        int flag; //讓跳值輪流用
        
        string ans = "";   
        
        max_increase = (numRows == 1) ? 1 : numRows * 2 - 2; 
       
        for(int i = 0; i < numRows; i++){
            
            int j = i; 
            
            inc0 = (i == numRows - 1) ? max_increase : max_increase - i * 2; //跳值1
            inc1 = (i == 0) ? max_increase : i * 2; //跳值2
            
            flag = 0;   
            
            while(j < s.length()){
                ans.push_back(s[j]); //儲存至ans
                
                j += (flag == 0)? inc0 : inc1; //輪流跳
                
                flag = flag^1;  //用xor翻轉旗標 (0->1, 1->0)
            }
            
        }
        return ans;
    }
};

https://ithelp.ithome.com.tw/upload/images/20201004/201291479VuhhzQrpI.png


上一篇
[LeetCode30] Day4 - 876. Middle of the Linked List
下一篇
[LeetCode30] Day20 -264. Ugly Number II
系列文
LeetCode3030
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言